package com.gitee.swsk33.algorithms.tree.huffmantree;

import java.util.ArrayList;
import java.util.List;

/**
 * 赫夫曼树测试类
 */
public class HuffmanTreeTest {

	/**
	 * 先序遍历二叉树
	 *
	 * @param root   待遍历二叉树的根
	 * @param result 存放结果的集合
	 */
	private static void preorderTraverse(TreeNodeWithWeight root, List<TreeNodeWithWeight> result) {
		if (root != null) {
			result.add(root);
			preorderTraverse(root.getLeft(), result);
			preorderTraverse(root.getRight(), result);
		}
	}

	/**
	 * 中序遍历二叉树
	 *
	 * @param root   待遍历二叉树的根
	 * @param result 存放结果的集合
	 */
	private static void inorderTraverse(TreeNodeWithWeight root, List<TreeNodeWithWeight> result) {
		if (root != null) {
			inorderTraverse(root.getLeft(), result);
			result.add(root);
			inorderTraverse(root.getRight(), result);
		}
	}

	public static void main(String[] args) {
		// 新建一些带权结点
		TreeNodeWithWeight<String> node1 = new TreeNodeWithWeight<>("a", 7, null, null);
		TreeNodeWithWeight<String> node2 = new TreeNodeWithWeight<>("b", 5, null, null);
		TreeNodeWithWeight<String> node3 = new TreeNodeWithWeight<>("c", 2, null, null);
		TreeNodeWithWeight<String> node4 = new TreeNodeWithWeight<>("d", 4, null, null);
		List<TreeNodeWithWeight<String>> nodes = new ArrayList<>();
		nodes.add(node1);
		nodes.add(node2);
		nodes.add(node3);
		nodes.add(node4);
		// 构建赫夫曼树
		HuffmanTree<String> tree = new HuffmanTree<>(nodes);
		// 先序遍历这个树看看
		List<TreeNodeWithWeight> result = new ArrayList<>();
		preorderTraverse(tree.getRoot(), result);
		System.out.print("先序遍历：");
		for (TreeNodeWithWeight node : result) {
			System.out.print(node.getData() + ":" + node.getWeight() + " ");
		}
		System.out.println();
		result.clear();
		inorderTraverse(tree.getRoot(), result);
		System.out.print("中序遍历：");
		for (TreeNodeWithWeight node : result) {
			System.out.print(node.getData() + ":" + node.getWeight() + " ");
		}
		System.out.println();
	}

}